package simple

import "ming/algorithm-for-go/leetcode/simple/model"

// sumRootToLeaf https://leetcode.cn/problems/sum-of-root-to-leaf-binary-numbers/
func sumRootToLeaf(root *model.TreeNode) int {
	var dfs func(node *model.TreeNode, count int) int
	dfs = func(node *model.TreeNode, count int) int {
		if node == nil {
			return 0
		}
		next := (count << 1) + node.Val
		if node.Left == nil && node.Right == nil {
			return next
		}
		return dfs(node.Left, next) + dfs(node.Right, next)
	}
	return dfs(root, 0)
}

func SumRootToLeafNotRecursion(root *model.TreeNode) int {
	var queue []*model.TreeNode
	queue = append(queue, root)
	cnt := 0
	for len(queue) > 0 {
		cur := queue[0]
		queue = queue[1:]
		if cur.Left != nil {
			cur.Left.Val = (cur.Val << 1) + cur.Left.Val
			queue = append(queue, cur.Left)
		}
		if cur.Right != nil {
			cur.Right.Val = (cur.Val << 1) + cur.Right.Val
			queue = append(queue, cur.Right)
		}
		if cur.Left == nil && cur.Right == nil {
			cnt += cur.Val
		}
	}
	return cnt
}
